//
// Created by 86131 on 2023/12/20.
//
#include "no_xiang_tu0.h"
//#include "bits/stdc++.h"
int main(){
    int numVertices ;
    int src,dest;
    int m;
    cin>>numVertices>>m;
    WeightedGraph_quan graph(numVertices);
    for(int i=0;i<m;i++){
        cin>>src>>dest;
        graph.addEdge(src-1,dest-1,1);
    }
    for(int j=0;j<numVertices;j++){
        double  sum=0;
        vector<int> weight;
        graph.Dijkstra(j,weight);
        for(int i=0;i<numVertices;i++){
            if(weight[i]<=6){
                sum++;
            }
        }
        sum = sum/numVertices;
        printf("%d: %.2f",j+1,sum*100);
        cout<<"%"<<endl;
    }
}
